By Arthur Ed LeBouthillier

This article was published in the September 1999 issue of The Robot Builder.

There are many different approaches to creating artificial intelligence in computers and, for our
purposes, intelligent robots. Since the founding of the field of Artificial Intelligence (AI), symbolic
approaches have persisted. Symbolic approaches represent problems as logical propositions between objects and use rules of logic to perform deductions. It is believed that by representing these relationships and reasoning about them, we can make computers perform similar mental feats as humans. This differs from non-symbolic techniques such as neural nets where often no consideration is given to how a problem is represented or solved as long as it is solved. Other trends away from symbolic AI approaches are some behavioral methods where there is no attempt to model the world internally. This article covers some of the basic ideas underlying symbolic AI; understanding these ideas is required to understand how more sophisticated AI
programs work and eventually implementing them AI techniques in robots.

First Order Logic

Classical logic has a long history and is well understood. With this historical basis, early AI
researchers created representations of logic that would allow  computers to perform logical
reasoning. First Order Logic was one of these developments. First Order Logic provides a method to store declarations about the world, the robot and everything it knows. There are limits to what it can represent, but you can go a long way before running into them. The limits it has are similar to the limits that exist on any programming language. Any given language can do what any other language can do, but sometimes it is harder to do some tasks in a given language. Rather than detail the theory in a mathematical way, let’s look at a simple problem using First Order Logic (FOL). Before that, let’s cover the basics.

First Order Logic Basics

The most basic elements of first order logic are a bunch of symbols. These symbols represent objects and relationships in the world. Examples of symbols are: Bob, Sam, Person, Hungry, Socrates, is-a, and a-kind-of. I think you’re already beginning to see the significance of these symbols. They are like words in a sentence.

The second element of first order logic is the way that symbols can be brought together to form
propositions. A proposition is a kind of sentence in the language of First Order Logic. First Order Logic describes a way to combine words (symbols) into sentences to make meaningful  propositions.  It specifies that a meaningful proposition has the structure of:

Proposition = Predicate(Arg_1, Arg_2, …, Arg_n)

The predicate describes the relationship between each of its arguments. The first argument in a
proposition is, by convention, the subject of the sentence and the second argument is usually the
object of the sentence (if it exists). Therefore, we could translate various sentences in the English language into propositions in First Order Logic:

The representational power of First Order Logic is very great and allows you to translate virtually any idea you can express in a sentence as a proposition. There are some problems with the ability to represent time-based changes, but there are often tricks one can perform to alleviate them.

Variables and Universal Qualifiers

We can also put variables into propositions, allowing a single proposition to stand for a whole class of propositions. A variable is merely a symbol
which is designated as being a variable. For our purposes, a variable will be represented as a symbolpreceded by a question mark (i.e. ?X). A Universal Qualifier is a compact notation for
asserting new facts from old ones. It represents a special technique one may apply to a list of
propositions to develop new facts. It is usually used in conjunction with variable-based propositions so that whole classes of new statements can be made. In classical logic, a Universal Qualifier has the structure of:

For All X, Proposition1 -> Proposition2

This is read as “For All X, Proposition one implies Proposition two.” Therefore, we could say that all Mammals are Vertebrates in a compact rule by asserting:

For All X, mammal(?X) -> Vertebrate(?X)

Using our First Order Logic representation and substituting “universally” for the “For All” part, we
could make the same statement:

Universally(mammal(?X), Vertebrate(?X))

Logical Combiners

We can also use And and Or modifiers to make more sophisticated statements. For example, a bird is a mammal which uniquely has feathers. This fact could be established by this rule:

Universally( mammal(?X) AND has-feathers(?X), bird(?X))

Deduction

Using the simple techniques outlined above, we can perform a function similar to deductive reasoning. A common example of deductive reasoning is: Knowing that Socrates is a Man and All men are mortal, we can conclude that Socrates is Mortal. By applying the universal rule listed below, we could deduce this in First Order Logic:

Start:
is-a(Socrates,Man)
Universally (is-a(?X, Man), Mortal(?X))

Result:
is-a(Socrates, Man)
Mortal(Socrates)

Deduction constitutes the major tool used in Expert Systems. By building up a list of propositions
(known as the Knowledge Base) with a list of rules (known as the rule base), expert systems are able to deduce new facts from what they already know. By including extensions for input and output, they allow the Expert System to interact with the world. Although expert systems are limited, they have proven themselves to be extremely useful in certain applications.

A Detailed Example

A more complete example of how to represent a complex description can be seen in the Cyc
knowledge base. The Cyc project is a multi-year attempt to encapsulate common-sense knowledge using a First Order Logic-like language, called CycL. It represents the most advanced attempt to make a knowledge base for artificial intelligence. In figure 1 is an example of relations from the concept “person.” The Cyc knowledge base has two major distinction related to sets. A thing that represents a subset of a set “generalizes” it and its relation predicate is genls. An element of a set uses the isa predicate.

The distinction between a set, a subset and an element of a set is an important thing to distinguish when reasoning about the world. If Fred is a person and a person is a collection (i.e. a collection of all people), Fred is not a collection. Fred, the element of the set Person is not equivalent to a set. Fred is an element of a set, not a set. There are not multiple instances of Fred walking around. If there were, they would be Fred1 and Fred2, elements of set Freds which would generalize person. Using genls and isa allows us to make these distinction.

We can see that Cyc (and thus First Order Logic) is able to represent many varied distinctions and traits that we understand about people (i.e. a person generalizes primate … generalizes mammal … generalizes vertebrate … generalizes animal). We can also understand that a person is an agent and that a person exists with some temporal properties (i.e. exists for a duration of time).

By applying various rules like deduction, we are able to resolve new facts that don’t explicitly exist
in the database. Cyc, using the CycL language, provides a whole suite of rules and functions which allow the basic propositions to resolve a much wider breadth of knowledge.

Knowledge and Robots

A robot using a complex knowledge base like Cyc or First Order Logic would be able to reason about many different aspects of the world. It could reason from first principles, reason about its goals, reason about interactions between its actions in the world and plan appropriately. Examples of working robots doing these things do exist in research labs. The Flakey robot of Stanford Research Institute has demonstrated some advanced reasoning capabilities. The NASA’s Remote Agent on the Deep Space One spacecraft is another. Of course, nothing we have discussed here addresses the issue of learning about the world or how that information is brought into the robot, but  the mechanism to reason with knowledge is well understood. Learning is an ongoing part of AI research and future robots should be able to convert
sensory information into symbolic representations of the world that they would then be able to reason with.

Summary

First Order Logic is an important tool for symbolic AI. It provides a mechanism to represent and
manipulate knowledge about the world in a computer usable form. Cyc is an example of a complex database using an extended version of First Order Logic.

;;; Agent
isa(Agent ExistingObjectType)
genls(Agent CompositeTangibleAndIntangibleObject)
;;; Animal
isa(Animal BiologicalKingdom)
genls(Animal PerceptualAgent)
genls(Animal AnimalBLO)
genls(Animal SolidTangibleThing)
genls(Animal Organism-Whole)
;;; BiologicalKingdom
isa(BiologicalKingdom BiologicalTaxonType)
genls(BiologicalKingdom BiologicalTaxon)
;;; BiologicalLivingObject
isa(BiologicalLivingObject ExistingObjectType)
genls(BiologicalLivingObject OrganicStuff)
genls(BiologicalLivingObject CompositeTangibleAndIntangibleObject)
;;; BiologicalOrder
isa(BiologicalOrder BiologicalTaxonType)
genls(BiologicalOrder BiologicalTaxon)
;;; CompositeTangibleAndIntangibleObject
isa(CompositeTangibleAndIntangibleObject ExistingObjectType)
genls(CompositeTangibleAndIntangibleObject PartiallyTangible)
genls(CompositeTangibleAndIntangibleObject PartiallyIntangible)
genls(CompositeTangibleAndIntangibleObject SomethingExisting)
;;; ExistingObjectType
isa(ExistingObjectType Collection)
genls(ExistingObjectType TemporalStuffType)
genls(ExistingObjectType ObjectType)
;;; IndividualAgent
isa(IndividualAgent ExistingObjectType)
genls(IndividualAgent Agent)
;;; Mammal
isa(Mammal BiologicalClass)
genls(Mammal Vertebrate)
;;; Omnivore
isa(Omnivore ExistingObjectType)
genls(Omnivore Organism-Whole)
;;; OrganismClassificationType
isa(OrganismClassificationType SiblingDisjointCollection)
genls(OrganismClassificationType ConventionalClassificationType)
genls(OrganismClassificationType ExistingObjectType)
;;; Organism-Whole
isa(Organism-Whole ExistingObjectType)
genls(Organism-Whole BiologicalLivingObject)
;;; PerceptualAgent
isa(PerceptualAgent ExistingObjectType)
genls(PerceptualAgent IndividualAgent)
;;; Person
isa(Person OrganismClassificationType)
genls(Person LegalAgent)
genls(Person Primate)
genls(Person HumanOccupationConstructResident)
genls(Person Omnivore)
;;; Primate
isa(Primate BiologicalOrder)
genls(Primate Mammal)
genls(Primate TerrestrialOrganism)
;;; Vertebrate
isa(Vertebrate BiologicalTaxon)
genls(Vertebrate Animal)

Figure 1 - An example of First Order Logic from Cyc